package com.berchen.算法.排序;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int size = 80000;
        int[] testArr = new int[size];
        for (int i = 0; i < size; i++) {
            testArr[i] = (int) (Math.random() * size);
        }

        Instant start=Instant.now();
        quickSort(testArr,0, testArr.length-1);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); // 56
//        System.out.println(Arrays.toString(testArr));
    }

    /**
     * 快速排序
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr, int start, int end) {

        int left=start;
        int right=end;
        int midValue=arr[(start+end)/2];    // 用来作为比较打基准值
        // 这里循环执行完成后 midValue左边打数据都比midValue小  右边打都大
        while (left<right){
            // 这里两个循环需要找到进行替换的数据
            while (arr[left]<midValue){
                left++;
            }
            while (arr[right]>midValue){
                right--;
            }
            if(left>=right){
                break;
            }

            // 交换数据
            arr[left]=arr[left]+arr[right];
            arr[right]=arr[left]-arr[right];
            arr[left]=arr[left]-arr[right];

            if(arr[left]==midValue){
                right--;
            }
            if(arr[right]==midValue){
                left++;
            }
        }
        if(left==right){
            left++;
            right--;
        }
        if(start<right){
            quickSort(arr,start,right);
        }
        if(left<end){
            quickSort(arr,left,end);
        }
    }
}
